package com.melo.dynamic;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 动态规划-背包问题
 * @date 2025-04-25
 */
public class Backpack {

    /**
     * 动态规划-背包问题
     *
     * @param objectWeightArr         背包中物品的重量
     * @param objectValueArr          背包中物品的价值
     * @param objectWeightAndValueArr 物品重量和价值的二维数组: 其中X轴表示不同的背包重量, Y轴表示放入不同的物品
     * @param storedObjectArr         放入背包的商品坐标
     */
    public static void dynamicBackpack(int[] objectWeightArr, int[] objectValueArr, int[][] objectWeightAndValueArr, int[][] storedObjectArr) {
        // 不处理第一行: 因为第一行默认都是0; 虚拟不同背包重量都没有放物品的场景
        for (int i = 1; i < objectWeightAndValueArr.length; i++) {
            // 不处理第一列: 因为第一列默认都是0; 虚拟背包重量为0, 且没有放任何物品的场景
            for (int j = 1; j < objectWeightAndValueArr[0].length; j++) {
                // 当前背包的容量小于本次要放入物品的重量
                if (objectWeightArr[i - 1] > j) {
                    // 直接使用前一个单元格的装入策略
                    objectWeightAndValueArr[i][j] = objectWeightAndValueArr[i - 1][j];
                } else {
                    /*
                     * 当前背包的容量大于等于本次要放入物品的重量: 取【前一个单元格装入的最大值】、【当前物品的价值+剩余背包容量的最大值】两者的最大值
                     * objectWeightAndValueArr[i - 1][j]: 前一个单元格装入的最大值
                     * objectValueArr[i - 1]: 当前物品的价值
                     * j - objectWeightArr[i - 1]: 减去当前物料的重量, 背包剩余的重量
                     * objectWeightAndValueArr[i - 1][j - objectWeightArr[i - 1]]: 背包减去当前物品的重量, 背包剩余容量能放入的最大价值
                     */
                    // objectWeightAndValueArr[i][j] = Math.max(objectWeightAndValueArr[i - 1][j], objectValueArr[i - 1] + objectWeightAndValueArr[i - 1][j - objectWeightArr[i - 1]]);
                    if (objectWeightAndValueArr[i - 1][j] > objectValueArr[i - 1] + objectWeightAndValueArr[i - 1][j - objectWeightArr[i - 1]]) {
                        objectWeightAndValueArr[i][j] = objectWeightAndValueArr[i - 1][j];
                    } else {
                        objectWeightAndValueArr[i][j] = objectValueArr[i - 1] + objectWeightAndValueArr[i - 1][j - objectWeightArr[i - 1]];
                        // 记录当前商品放入背包
                        storedObjectArr[i][j] = 1;
                    }
                }
            }
        }
    }
}
